package main.java.indi.zyj.hot100;

import java.util.ArrayDeque;
import java.util.Deque;

public class _10_maxSlidingWindow {

    public int[] maxSlidingWindow1(int[] nums, int k) {


        int len = nums.length;
        int[] res = new int[len - k + 1];

        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < len; i++) {
            int curNum = nums[i];
            while (!deque.isEmpty() && curNum >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);
            if (i - deque.getFirst() == k) {
                deque.removeFirst();
            }
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()];
            }
        }

        return res;

    }


    public int[] maxSlidingWindow(int[] nums, int k) {

        int length = nums.length;
        int[] result = new int[length - k + 1];

        // 维护队列从大到小顺序
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < length; i++) {
            // 当前遍历元素值
            int curNum = nums[i];
            // 出队
            while (!deque.isEmpty() && nums[deque.getLast()] <= curNum) {
                deque.removeLast();
            }
            // 入队
            deque.addLast(i);
            // 等于窗口 k 时，移除队首
            if (i - deque.getFirst() == k) {
                deque.removeFirst();
            }
            // 等于窗口k,就需要记录窗口内最大元素了
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return result;
    }
}
